package com.xiaoyu.string;

import java.util.HashMap;

/**
 * @program: DS_and_A
 * @description: 无重复字符的最长子串
 *
 * 给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
 *
 * 输入: s = "abcabcbb"
 * 输出: 3
 * 解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
 *
 * @author: YuWenYi
 * @create: 2021-05-26 08:21
 **/
public class LengthOfLongestSubstring_3 {

    /*思路:
    * 1.使用hashmap记录以及出现过的字符
    * 2.注意是子串,子串必须全部连在一起字符串
    * 3.一但出现重复字符,就需要将指针回溯到该重复字符的索引+1的位置
    * 4.一但后面子串的长度大于前面的,那么就需要进行替换
    * */
    public static int lengthOfLongestSubstring(String s) {
        int fast = 0;
        int subLen = 0,tempLen=0;
        HashMap<Character, Integer> map = new HashMap<>();
        char[] chars = s.toCharArray();
        while (fast < chars.length){
            if (!map.containsKey(chars[fast])) {
                tempLen++;
            } else {
                if (tempLen > subLen) {
                    subLen = tempLen;
                }
                //临时长度变成1,因为当前元素虽然是之前的重复元素,但是对于新的子串来说,这属于第一个元素
                tempLen = 1;
                //快指针回到出现该重复元素的索引+1的地方,从它开始继续找第二个子串
                fast = map.get(chars[fast]) + 1;
                //推倒重来,map清除
                map.clear();
            }
            map.put(chars[fast],fast);
            fast++;
        }
        //如果最后一段字符串整体都是无重复子串,那么最后就会退出for循环而没有进入else的判断改长度,因此在这里需要补一下
        if (tempLen > subLen) {
            subLen = tempLen;
        }
        return subLen;
    }


    //官方题解: 滑动窗口 + 双指针!
    //left指针代表子串的起始位置,right指针代表无重复子串的末尾位置,在没有出现重复字符之前,right++,出现之后,left++
    //left会依次遍历整个字符串的所有字符,这样整完一次后,找出最长子串就是答案
    public static int lengthOfLongestSubstring1(String s) {
        HashMap<Character, Integer> map = new HashMap<>();
        int res = 0,left = 0;
        char[] chars = s.toCharArray();
        for (int right = 0; right < chars.length; right++) {
            /*对于Math.max(map.get(chars[right]) + 1, left)的解释!
             1、首先，判断当前字符是否包含在map中，如果不包含，将该字符添加到map（字符，字符在数组下标）,
             此时没有出现重复的字符，左指针不需要变化。此时不重复子串的长度为：i-left+1，与原来的maxLen比较，取最大值；

             2、如果当前字符 ch 包含在 map中，此时有2类情况：
             1）当前字符包含在当前有效的子段中，如：abca，当我们遍历到第二个a，当前有效最长子段是 abc，我们又遍历到a，
             那么此时更新 left 为 map.get(a)+1=1，当前有效子段更新为 bca；
             2）当前字符不包含在当前最长有效子段中，如：abba，我们先添加a,b进map，此时left=0，我们再添加b，发现map中包含b，
             而且b包含在最长有效子段中，就是1）的情况，我们更新 left=map.get(b)+1=2，此时子段更新为 b，而且map中仍然包含a，map.get(a)=0；
             随后，我们遍历到a，发现a包含在map中，且map.get(a)=0，如果我们像1）一样处理，就会发现 left=map.get(a)+1=1，实际上，left此时
             应该不变，left始终为2，子段变成 ba才对。

             为了处理以上2类情况，我们每次更新left，left=Math.max(left , map.get(ch)+1).
             另外，更新left后，不管原来的 s.charAt(i) 是否在最长子段中，我们都要将 s.charAt(i) 的位置更新为当前的i，
             因此此时新的 s.charAt(i) 已经进入到 当前最长的子段中！
             */
            if (map.containsKey(chars[right])){
                left = Math.max(map.get(chars[right]) + 1, left);
            }
            map.put(chars[right],right);
            res = Math.max(res, right-left+1);
        }
        return res;
    }

    public static void main(String[] args) {
        int i = lengthOfLongestSubstring1("abcabcdbb");
        System.out.println(i);
    }
}
